剑指offer 13——机器人的运动范围

这道题本质还是搜索，因此可以使用深度优先搜索和广度优先搜索进行解决。

原题

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

输入：m = 2, n = 3, k = 1
输出：3
示例 2：

输入：m = 3, n = 1, k = 0
输出：1

提示：

1 <= n,m <= 100
0 <= k <= 20

原题url：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

解题

深度优先搜索

从一个点出发，遍历完所有点，为了保证不会重复遍历，因此我们可以借助一个二维矩阵记录已经遍历过的点。而用深度优先搜索遍历的话，一般都是使用递归的。

需要注意的是，虽然机器人可以上下左右移动，但因为是从[0, 0]开始的，所以可以想象成根节点往子节点或兄弟节点的遍历方式，深度优先搜索就是先遍历子节点，子节点遍历完成后，在遍历兄弟节点。

终止条件应该有：

坐标越界，也就是 x >= m 或者 y >= n 。
该点已经访问过，既然访问过，自然不用重新计算。
坐标数字之和大于 k

求数字各数位之和，最简单的方法应该就是 摸除% + 整除/ 就可以了。

我们来看看代码：

class Solution {
    public int movingCount(int m, int n, int k) {
        int result = 0;
        int max = m > n ? m : n;
        // key为数字，value为该数字各位之和
        Map<Integer, Integer> numMap = new HashMap<>(max * 4 / 3 + 1);
        // 记录已经访问过的节点
        boolean[][] visited = new boolean[m][n];
        // 从(0, 0)开始移动
        return move(0, 0, m, n, k, numMap, visited);
    }

    public int move(int x, int y, int m, int n, int k, Map<Integer, Integer> numMap, boolean[][] visited) {
        // 是否越界
        if (x >= m || y >= n) {
            return 0;
        }

        // 如果该节点已经访问过
        if (visited[x][y] == true) {
            // 说明该方格所代表的次数已经被计算过，因此返回0
            return 0;
        }

        // 标记该节点已经访问过
        visited[x][y] = true;
        // 计算
        int xSum = getNumSum(x, numMap);
        int ySum = getNumSum(y, numMap);
        if (xSum + ySum > k) {
            return 0;
        }

        // 尝试向下、向右
        return 1 + move(x + 1, y, m, n, k, numMap, visited) + move(x, y + 1, m, n, k, numMap, visited);
    }

    public int getNumSum(int num, Map<Integer, Integer> numMap) {
        Integer sum = numMap.get(num);
        if (sum != null) {
            return sum;
        }

        int key = num;
        sum = 0;
        while (num != 0) {
            sum += num % 10;
            num = num / 10;
        }
        numMap.put(key, sum);
        return sum;
    }
}

提交OK。我们来看看这种方法的复杂度：

时间复杂度 O(MN) ：最差情况下，机器人遍历矩阵所有单元格，此时时间复杂度为 O(MN)。
空间复杂度 O(MN) ： visited 矩阵的大小就是 mn，因此使用了 O(MN) 的额外空间。

广度优先搜索

广度优先搜索，也就是从根节点出发，先遍历兄弟节点，再遍历子节点。一般我们都需要借助一个队列存储已经即将要遍历的节点，因为队列的特性是先进先出，因此当父节点遍历完成后，会依序遍历所有该父节点的所有子节点（这些节点都是兄弟），再遍历下一层的子节点。

（PS：现在想想，如果用栈存储已经遍历过的节点，也是可以的，只是访问节点的方式并没有什么规律可言。）

针对该机器人的运动，也是从 [0, 0] 出发，向下向右移动，层层递进。

接下来我们看看代码：

class Solution {
    public int movingCount(int m, int n, int k) {
        int result = 0;
        int max = m > n ? m : n;
        // key为数字，value为该数字各位之和
        Map<Integer, Integer> numMap = new HashMap<>(max * 4 / 3 + 1);
        // 记录已经访问过的节点
        boolean[][] visited = new boolean[m][n];
        // 记录还未访问结束的点
        Queue<Coordinate> queue = new LinkedList<>();
        // 从(0, 0)开始移动
        queue.offer(new Coordinate(0, 0));
        while (!queue.isEmpty()) {
            // 获取队首元素
            Coordinate coordinate = queue.poll();
            // 判断当前坐标是否有效
            if (coordinate.x >= m || coordinate.y >= n) {
                continue;
            }
            // 判断当前左边是否已经访问过
            if (visited[coordinate.x][coordinate.y]) {
                continue;
            }
            // 标记当前坐标已经访问过
            visited[coordinate.x][coordinate.y] = true;
            // 判断当前坐标是否有效
            int xSum = getNumSum(coordinate.x, numMap);
            int ySum = getNumSum(coordinate.y, numMap);
            if (xSum + ySum > k) {
                continue;
            }
            // 如果有效
            result++;
            // 将下边一格节点放入队列中
            queue.add(new Coordinate(coordinate.x + 1, coordinate.y));
            // 将右边一格节点放入队列中
            queue.add(new Coordinate(coordinate.x, coordinate.y + 1));
        }
        return result;
    }

    public int getNumSum(int num, Map<Integer, Integer> numMap) {
        Integer sum = numMap.get(num);
        if (sum != null) {
            return sum;
        }

        int key = num;
        sum = 0;
        while (num != 0) {
            sum += num % 10;
            num = num / 10;
        }
        numMap.put(key, sum);
        return sum;
    }

    class Coordinate {
        int x;
        int y;
        
        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

提交OK。我们来看看这种方法的复杂度：

时间复杂度 O(MN) ：最差情况下，机器人遍历矩阵所有单元格，此时时间复杂度为 O(MN)。
空间复杂度 O(MN) ： visited 矩阵的大小就是 mn，因此使用了 O(MN) 的额外空间。

既然上下两种方法时间复杂度相同，但比较奇怪的在于，我在力扣上提交时，上面一种方法所花费的时间是 1ms ，但这种方法所花费的时间是 7ms 。既然复杂度的计算是忽略了系数、低阶、常数，但我认为上下两种方法即使不忽略，应该也是一样的。 如果你有新的看法，欢迎指教。

求坐标之和

求坐标之和的方法，我写的是比较简单的一种，但如果你好好想想，就可以发现有更简单的方法。

正常情况下，随着数字逐渐变大，数字各位之和应该也是逐渐上升的，但唯一的特殊情况就是 进位 ，比如 19 变到 20 ，各数位之和从 10 变为 2，其实细心点就可以发现，十位数虽然加1，但个位数减9，因此总体减8。所以可以总结出：

1 2	假设现在的数字为x，其各位数之和为Sum(x)，那么下一个Sum(x + 1)为： Sum(x + 1) = ((x + 1) % 10 == 0) ? (Sum(x) - 8) : (Sum(x) + 1)

那么上面的代码还有可以优化的地方，这个就留给大家去完成了。